#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define mes(x) memset(x,0,sizeof(x))
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout)

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int MAXN = 3e3+10;

int n,m;
int h[MAXN],dis[MAXN],v[MAXN];
bool vis[MAXN];
struct node{int v,w;};
vector <node> G[MAXN];

void spfa(int x){
	queue <int> q; memset(dis,0x3f,sizeof(dis));
	dis[x] = 0;v[x] = 1; q.push(x);
	while(q.size()){
		int x = q.front();q.pop();
		vis[x] = 0;v[x]++; if(v[x] >= n) {puts("-1");exit(0);}
		for(auto d : G[x]){
			int y = d.v,w = d.w;
			if(dis[x] + w < dis[y]){
				dis[y] = dis[x] + w;
				if(!vis[y]) q.push(y),vis[y] = 1;
			}
		}
	}
}

void dijk(int x){
	priority_queue<pii> q; mes(vis); memset(dis,0x3f,sizeof(dis));
	q.push(pii(0,x)); dis[x] = 0;
	while(q.size()){
		int x = q.top().se;q.pop(); if(vis[x]) continue;
		vis[x] = 1;
		for(auto d : G[x]){
			int y = d.v,w = d.w + h[x] - h[y];
			if(dis[x] + w < dis[y]){
				dis[y] = dis[x] + w;
				q.push(pii(-dis[y],y));
			}
		}
	}
}

int main (){
	n = in,m = in;
	for(int i = 1;i <= m;i++) {int x = in,y = in,w = in;G[x].push_back((node){y,w});}
	for(int i = 1;i <= n;i++) G[0].push_back((node){i,0});
	spfa(0); ll ans = 0;
	for(int i = 1;i <= n;i++) h[i] = dis[i];
	for(int i = 1;i <= n;i++){
		dijk(i);
		ans = 0;for(int j = 1;j <= n;j++) ans += 1ll * j * min((int)1e9,(dis[j] - h[i] + h[j]));
		printf("%lld\n",ans);
	}
	return 0;
}

